1. Field of the Invention
The present invention relates to a method and apparatus for identifying a fingerprint, and more particularly, to a method and apparatus for identifying a user's fingerprint for automatic personal identification, based on a large capacity of database, using geometric hashing and parallel processing.
2. Description of the Related Art
In general, a personal identification system requires users to present their identifiers (IDs) and passwords for authentication, thus causing user's inconvenience. An automated fingerprint identification system alleviates this inconvenience and is very reliable since it is capable of identifying users based on their fingerprints. Thus, the automated fingerprint identification system can substitute for such a personal identification system. The automated fingerprint identification system has been applied to an entry control system that provides physical security, and a computer security system that provides security via a network system, thus enabling electronic commerce such as on-line banking. Further, the automated fingerprint identification system has been used for criminal identification and immigration control.
Most conventional automated fingerprint identification systems perform two steps of enrolling and identifying users' fingerprints. In the fingerprint enrollment, fingerprints of a plurality of users are classified into ten or less categories for quick processing and then enrolled in a central database according to the categories. In general, fingerprints are classified into an arch type, a left loop type, a right loop type, a whorl type, and a tented arch type according to their shapes. After the enrollment, in the fingerprint identification, when a user's fingerprint is input for identification, its shape is examined to detect a category to which the input fingerprint belongs and the input fingerprint is compared with fingerprints belonging to the detected category to determine similarities therebetween. The fingerprint identification further includes fingerprint alignment and matching, thus increasing computational complexity. In particular, the fingerprint alignment results in computational complexity since there is no reference point for the comparison of fingerprints.
An automated fingerprint identification method and system is disclosed in a paper entitled “A Real-Time Matching System for Large Fingerprint Databases” (IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, No. 8, August 1996); U.S. Pat. No. 5,572,597 entitled “Fingerprint Classification System”; and U.S. Pat. No. 5,825,907 entitled “Neural Network System for Classifying Fingerprints”.
In the paper entitled “A Real-time Matching System for Large Fingerprint Databases”, minutiae points of fingerprints of two users are extracted from a large capacity of database for fingerprint identification. The extracted minutiae points are amended to be matched. When determining similarity between the minutiae points based on a result of comparing their phases, it is required to extract fingerprints located at the same position and in the same direction so as to increase precision of the result of comparing. However, in general, it is difficult to exactly identify fingerprints because they have different phases and directions. Therefore, it is required to compensate the differences in phase and direction. Hough Transform may be used to compensate the differences in phase and direction.
In detail, sections of memory are allocated as three-dimensional bins that store difference values between locations and directions of respective pairs of minutiae points. Next, the difference values between the respective pairs of minutiae points are calculated and stored in the respective bins. Thereafter, a bin storing a maximum difference value is detected. The bin is set to be a difference of locations and directions between two fingerprints, and then the compensation for the two fingerprints is accomplished by using the bin. However, the compensation requires a large capacity of memory, and further, the more a number of users whose fingerprints are enrolled in the database, the lower the performance of the method.
U.S. Pat. Nos. 5,572,597 and 5,825,907 disclose automated fingerprint identification systems in which fingerprints are classified into a plurality of groups according to their shapes and stored in a large capacity of database for speedy identification. Next, when a fingerprint is input for identification, its shape is analyzed to detect a group, to which the input fingerprint belongs, from the database and fingerprint identification is performed on only the input fingerprint and a set of fingerprints belonging to the group. However, in this case, when fingerprints are improperly classified, it is impossible to identify the input fingerprint.
Such conventional automated fingerprint identification systems have the following disadvantages. First, they require a large amount of time to perform fingerprint identification, in particular, fingerprint alignment, when a number of users whose fingerprints are enrolled in a database is increased. Thus, it is impossible to identify fingerprints from a large of database in real time. Second, when fingerprints are inappropriately classified, it is impossible to exactly perform fingerprint identification. Third, the conventional automated fingerprint identification systems further require various information regarding fingerprints, in addition to their minutiae points, for an accurate fingerprint comparison, thus resulting in consumption of a large storage space of a center database.